Computer and network systems often employ caching techniques to improve system performance and return data to a client faster than if the data came from storage directly. Some cache systems involve multiple caches, or cache nodes, that store different data based on a storage policy. For example, one cache node may store airfare search results, while another stores hotel search results, and yet another stores rental car search results. Using the storage policy, routers intelligently route client requests to the appropriate cache node based on the search. If the results are found, they are returned to the client. If the results are not found, the client must search somewhere else. Once the data is found, it is stored in the cache node for future reference, according to the storage policy.
Over time, the data stored in the cache node is removed or replaced, which may also be referred to as an “eviction.” Various techniques can be used to determine which data to evict. For example, some cache systems remove data from a cache node once the data has changed in a corresponding database. Other cache systems evict data after it has expired, i.e., after a certain time has elapsed since a first search returned said data, after there has been no request for the data after a certain time, etc.
Unfortunately, at times there is more data to store than the cache node can accommodate. Even though the cache node is evicting the expired data, more data is being added to the cache node than removed. In these instances, cache nodes run the risk of running out of storage space and either randomly deleting data, without knowing how old the deleted data are of if they should be evicted, or not storing the new data. Thus, the cache node may delete data that should remain, while leaving entries that should be evicted.